package offer;

public class offerII_0102 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        int len=nums.length;
        for(int i=0;i<len;++i){
            sum+=nums[i];
        }
        if((sum+target)%2==1) return 0;
        target=(sum+target)/2;
        int[][] dp=new int[len][target+1];
        if(nums[0]<=target){
            dp[0][nums[0]]=1;
        }
        if(nums[0]==0) dp[0][0]=2;
        else dp[0][0]=1;

        for(int i=1;i<len;++i){
            if(nums[i]>0){
                dp[i][0]=dp[i-1][0];
            }
            else dp[i][0]=dp[i-1][0]*2;
        }
        for(int i=1;i<len;++i){
            for(int j=1;j<target+1;++j){
                if(nums[i]>j){
                    dp[i][j]=dp[i-1][j];
                }
                else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
            }
        }
        return dp[len-1][target];
    }
}
